| 翻訳と辞書 |
| graph structure theorem ： ウィキペディア英語版 |
graph structure theorem
In mathematics, the graph structure theorem is a major result in the area of graph theory. The result establishes a deep and fundamental connection between the theory of graph minors and topological embeddings. The theorem is stated in the seventeenth of a series of 23 papers by Neil Robertson and Paul Seymour. Accordingly, its proof is very long and involved. and are surveys accessible to nonspecialists, describing the theorem and its consequences.
== Setup and motivation for the theorem ==
A minor of a graph ''G'' is any graph ''H'' that is isomorphic to a graph that can be obtained from a subgraph of ''G'' by contracting some edges. If ''G'' does ''not'' have a graph ''H'' as a minor, then we say that ''G'' is ''H''-free. Let ''H'' be a fixed graph. Intuitively, if ''G'' is a huge ''H''-free graph, then there ought to be a "good reason" for this. The graph structure theorem provides such a "good reason" in the form of a rough description of the structure of ''G''. In essence, every ''H''-free graph ''G'' suffers from one of two structural deficiencies: either ''G'' is "too thin" to have ''H'' as a minor, or ''G'' can be (almost) topologically embedded on a surface that is too simple to embed ''H'' upon. The first reason applies if ''H'' is a planar graph, and both reasons apply if ''H'' is not planar. We first make precise these notions.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「graph structure theorem」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|